<!DOCTYPE html>
<html lang="zh-cn">
<head>
    <title>排列与组合</title>
    <meta charset="utf-8" />
    <link rel="stylesheet" type="text/css" href="../../css/note.css" />
</head>
<body>

<h2>组合数</h2>

<h3>定义与例子</h3>

<p class="definition">
	若集合 (或多重集) `Y sube X`, 且 `|Y| = m`, 则称 `Y` 是 `X` 的一个
	<b>`bm m`-子集</b>.
	设 `n, m` 是非负整数, `m le n`,
	定义 `n` 选 `m` 的<b>组合数</b>为集合 `X_n = {1, 2, cdots, n}` 的
	`m`-子集数, 记为
	<span class="formula">
		`(n;m) = C(n, m) = C_n^m`.
	</span>
	这里的字母 C 可理解为 choice 或 combination.
	特别地, `(n;0) -= 1`, 因为大小为 0 的子集只有空集;
	`(n;n) -= 1`, 因为大小为 `n` 的子集只能是 `X_n` 自身.
	组合数最直观的解释是, 从 `n` 件不同物品中选出 (无序的) `m` 件的方法数.
</p>

<p>
	有了组合数的概念, 第二类计数问题 `F_2, I_2, S_2` 就都得到了解决.
</p>

<p class="example">
	考虑十二重计数问题之 `I_2`, 即将 `m` 件相同物体放入 `n`
	个不同盒子, 且使得每个盒子的物体数只能是 0 或 1 的方法数.
	显然只需从 `n` 个盒子选出物体数为 1 的盒子即可. 故
	<span class="formula">
		`|I_2| = (n;m)`.
	</span>
</p>

<ol class="example">
	考虑十二重计数问题之 `S_2`, 即将 `m` 件相同物体放入 `n`
	个不同盒子, 且使得每个盒子不空的方法数.
	换个角度来看, 要将物体分为有序的 `n` 份, 只需在物体间插入 `n-1`
	个隔板即可. 比如, 将 10 个 <code>o</code> 放进 6 个不同的盒子,
	只需在它们之间插入 5 个隔板:
	<span class="formula">
		<code>o|oo|ooo|o|o|oo</code>
	</span>
	需要注意, 和物体一样, 这里的隔板是不可区分的对象.
	由于每个盒子不空, 问题转化为在 `m-1` 个空隙中插入 `n-1`
	个隔板的方法数, 于是
	<span class="formula">
		`|S_2| = (m-1;n-1)`.
	</span>
	`|S_2|` 还是:
	<li>方程 `sum_(i=1)^n x_i = m` 的正整数解的个数;</li>
    <li>用数字 `1~n` 组成的长度为 `m` 的严格递增序列数.</li>
</ol>

<ol class="example">
	考虑十二重计数问题之 `F_2`, 即将 `m` 件相同物体放入 `n`
	个不同盒子的总方法数. 考虑 `n-1` 个隔板,
	由于盒子可以为空, 这些隔板和物体之间的次序也是任意的. 比如将 10 个
	<code>o</code> 放进 6 个不同的盒子的一种方法是:
	<span class="formula">
		<code>o||oo|||ooooooo</code>
	</span>
	问题转化为将 `n-1` 个隔板与 `m` 件物体排成一行的组合数.
	注意隔板与物体都不可区分, 这相当于在
	`m+n-1` 个位置上选出 `m` 个物体, 即
	<span class="formula">
		`|F_2| = (m+n-1;m)`.
	</span>
	`|F_2|` 还是:
	<li>方程 `sum_(i=1)^n x_i = m` 的非负整数解的个数;</li>
	<li>多重集 `{oo * 1, oo * 2, cdots, oo * n}` 的 `m`-子集数;</li>
    <li>用数字 `1~n` 组成的长度为 `m` 的 (不严格的) 递增序列数.</li>
</ol>

<h3>组合数的计算, Pascal (杨辉) 三角</h3>

<p>	我们推导组合数的一些简单性质.
	下面所推导的恒等式, 有些没有给出参数 `n, m, k` 等的取值范围,
	这时按照组合数的定义考虑它们的范围即可.
</p>

<p class="property">
  <b>对称性</b> `(n;k) = (n;n-k)`.
</p>

<p class="proof">
	组合证明: 设 `|X| = n`, 因为 `X` 的每个子集 `Y` 和它的余集 `X \\ Y`
	一一对应, 所以选出 `k`-子集的方法数等于选出 `n-k`-子集的方法数.
</p>

<p class="property">
  <b>选班长恒等式</b> `(n;k) = n/k (n-1;k-1)`.
</p>

<p class="proof">
  [来自 widcardw] 组合证明:
  在 `n` 个人中选出 `k` 个班委, 再从班委中选出一个班长, 方法数为
  `(n;k) k`; 另一方面, 在 `n` 个人中选出一个班长, 再从剩下 `n-1` 人中选出
  `k-1` 个班委, 方法数为 `n (n-1;k-1)`.
</p>

<p class="property">
  <b>Pascal 恒等式</b> `(n+1;k) = (n;k-1) + (n;k)`.
</p>

<p class="proof">
	组合证明:
	事先将 `n+1` 件物品标号为 `1, 2, cdots, n+1`.
	现从 `n+1` 件物品中选取 `k` 件, 如果其中含有第一件物品,
	则需要从剩下 `n` 件中再选取 `k-1` 件, 有 `(n;k-1)` 种选法;
	如果其中不含第一件物品, 则需要从剩下 `n` 件中选取 `k` 件,
	有 `(n;k)` 种选法.
</p>

<p class="example">
	<b>Pascal (杨辉) 三角</b>
	利用 `(n;0) = (n;n) = 1` 和 Pascal 恒等式,
	将组合数列成一个等腰三角形数表:
	<span class="formula">
		`(0;0)`<br/>
		`(1;0) quad (1;1)`<br/>
		`(2;0) quad (2;1) quad (2;2)`<br/>
		`(3;0) quad (3;1) quad (3;2) quad (3;3)`<br/>
		`(4;0) quad (4;1) quad (4;2) quad (4;3) quad (4;4)`<br/>
		`(5;0) quad (5;1) quad (5;2) quad (5;3) quad (5;4) quad (5;5)`<br/>
		`cdots`
	</span>
	即
	<span class="formula">
		`1`<br/>
		`1 quad 1`<br/>
		`1 quad 2 quad 1`<br/>
		`1 quad 3 quad 3 quad 1`<br/>
		`1 quad 4 quad 6 quad 4 quad 1`<br/>
		`1 quad 5 quad 10 quad 10 quad 5 quad 1`<br/>
		`cdots`
	</span>
	其中三角形两腰上的数都等于 1,
	数表中任意其它数都等于它的直接左上和直接右上方的数字之和.
</p>

<h2>组合恒等式</h2>

<p>	这里收集一些关于组合数 `(n;m)` 的恒等式.
	约定 `0^0 = 1`, `sum_(i=k)^(k-1) = 0`, `prod_(i=k)^(k-1) = 1`.
</p>

<p class="theorem">
	<b>二项式定理</b>
	`n` 为非负整数, `x, y` 为任意实数, 则
	<span class="formula">
		`(x+y)^n = sum_(k=0)^n (n;k) x^k y^(n-k)`.
	</span>
	因此组合数 `(n;k)` 也称为<b>二项式系数</b>.
</p>

<p class="corollary">
	在二项式定理中取 `x = y = 1` 有
	<span class="formula">
		`2^n = sum_(k=0)^n (n;k)`.
	</span>
	取 `x = 1`, `y = -1` 有
	<span class="formula">
		`0 = sum_(k=0)^n (n;k) (-1)^k`,
	</span>
	即
	<span class="formula">
		`sum_(k" is odd") (n;k) = sum_(k" is even") (n;k)`.
	</span>
</p>

<p class="theorem" id="the-vandermonde">
	<b>Vandermonde 恒等式</b>
	`m, n` 为非负整数, 则
	<span class="formula">
		`(m+n;k) = sum_(i=0)^k (m;i)(n;k-i)`.
	</span>
</p>

<p class="corollary">
	在 Vandermonde 恒等式中令 `m = n = k` 有
	<span class="formula">
		`(2n;n) = sum_(i=0)^n (n;i)^2`.
	</span>
</p>

<p class="theorem">
	<b>朱世杰恒等式 (元代)</b>
	设 `m, n` 为非负整数, 则
	<span class="formula">
		`(m+n+1;n+1) = sum_(i=0)^m (n+i;n)`.
	</span>
	令 `n = k`, `m = n-k`, 得左斜公式:
	<span class="formula">
		`(n+1;k+1) = sum_(i=0)^(n-k) (k+i;k)`
		`= sum_(i=k)^n (i;k)`.
	</span>
	令 `m = k`, `n = m-k`, 得右斜公式:
	<span class="formula">
		`(m+1;k) = sum_(i=0)^k (m-k+i;i)`
		`= sum_(i=0)^k (m-i;k-i)`.
	</span>
</p>

<div class="proof">
	注意到朱世杰恒等式实质上是将 Pascal 三角的系数按左斜线相加,
<pre>
            1
		  1  (1)
		1  (2) [1]
	  1  (3)  3   1
	1  (4)  6   4   1
  1  (5)  10  10  5   1
</pre>
	如, 为了将括号中的数字相加, 将右上角的 1 换成方括号中的 1,
	就可以反复应用 Pascal 恒等式: 1 + 2 = 3, 3 + 3 = 6 ...,
	最后得到所求的和 15. 为此得到启发,
	反复用 Pascal 恒等式:
	<span class="formula">
		右边 `= (n+1;n+1) + sum_(i=1)^m (n+i;n)`
		`= (n+2;n+1) + sum_(i=2)^m (n+i;n)`
		`= cdots =` 左边.
	</span>
</div>

<p class="example">
	设 `m, n` 是非负整数, `m gt n`, 则
	<span class="formula">
		`sum_(i=0)^n {:(n;i):}/{:(m;i):} = (m+1)/(m+1-n)`.
	</span>
</p>

<p class="proof">
	应用右斜公式:
	<span class="formula">
		左边 `= 1/{:(m;n):} sum_(i=0)^n (m-i;n-i)`
		`= {:(m+1;n):}/{:(m;n):} =`
		右边.
	</span>
</p>

<p class="example">
  [来自 概率论课本] 关于 Pascal 分布的恒等式
  <span class="formula">
    `sum_(k ge n) (m+k-1; k) p^k q^m`
    `= sum_(k=0)^(m-1) (n+m-1; k) p^(n+m-1-k) q^k`
    `= sum_(k=0)^(m-1) (n+k-1; k) p^n q^k`.
  </span>
  其中 `p+q = 1`.
</p>

<ol class="proof">
  上式记为 (1) = (2) = (3).
  <li>先证 (2) = (3). 将 `p^(m-1-k) = (1-q)^(m-1-k)` 二项展开得
    <span class="formula">
      `(2) // p^n`
      `= sum_(k=0)^(m-1) (n+m-1; k) p^(m-1-k) q^k`
      `= sum_(k=0)^(m-1) (n+m-1; k) q^k sum_(j=0)^(m-1-k) (m-1-k; j) (-q)^j`
    </span>
    令 `t = j+k`, 利用负二项系数 `(m-1-k; j) (-1)^j = (j+k-m; j)`, 上式等于
    <span class="formula">
      `sum_(t=0)^(m-1) q^t sum_(j=0)^t (n+m-1; t-j) (t-m; j)`.
    </span>
    最后利用 Vandermonde 恒等式, 上式等于
    <span class="formula">
      `sum_(t=0)^(m-1) q^t (n-1+t; t) = (3) // p^n`.
    </span>
  </li>
  <li>再证 (1) = (2).
    注意到
    <span class="formula">
      `(1) = sum_(k ge n) (-m; k) (-p)^k q^m`
      `= (1-p)^-m q^m - sum_(k=0)^(n-1) (-m; k) (-p)^k q^m`
      `= 1 - sum_(k=0)^(n-1) (m+k-1; k) p^k q^m`,<br>
      `(2) = (p+q)^(n+m-1) - sum_(k=m)^(n+m-1) (n+m-1; k) p^(n+m-1-k) q^k`
      `= 1 - sum_(k=0)^(n-1) (n+m-1; k) p^k q^(n+m-1-k)`.
    </span>
    再由 (2) = (3) 即知 (1) = (2).
  </li>
</ol>

<p class="example">
  [来自 卡尔・夏洛克]
  证明 `sum_(k=0)^n 1/(n-k)! sum_(i=0)^k (-1)^i/i! = 1`.
</p>

<p class="proof">
  先倒序求和 `k mapsto n-k`, 再令 `j = i+k`: 原式等于
  <span class="formula">
    `sum_(k=0)^n 1/k! sum_(i=0)^(n-k) (-1)^i/i!`
    `= sum_(j=0)^n sum_(i=0)^j (-1)^i/((j-i)!i!)`
    `= sum_(j=0)^n 1/j! sum_(i=0)^j (j;i) (-1)^i`
    `= 1 + sum_(j=1)^n 1/j! (1-1)^j`
    `= 1`.
  </span>
</p>

<h2>多重指标运算与多项展开</h2>

<p class="definition">
  <b>多重指标</b> 是一个整数向量 `alpha = (alpha_1, alpha_2, cdots,
  alpha_n)`, 它的运算规则如下:
  <span class="formula">
    `alpha +- beta` 就是一般向量的加减法,<br/>
    `alpha le beta` `iff alpha_i le beta_i`, `AA i`,<br/>
    `|alpha| = sum alpha_i`,<br/>
    `alpha! = prod alpha_i!`, `quad alpha ge 0`,<br/>
    `(alpha; beta) = (alpha!)/(beta!(alpha-beta)!)`
    `= prod (alpha_i; beta_i)`, `quad alpha ge beta ge 0`.
  </span>
  在多元微分学中, 设 `x = (x_1, cdots, x_m)`, 可以定义
  <span class="formula">
    `x^alpha = prod x_i^(alpha_i)`,<br/>
    `D^alpha = prod D_i^(alpha_i)`, `quad D_i^j = del^j/(del x_i^j)`.
  </span>
</p>

<p class="corollary">
  设 `n, k` 为多重指标, 则
  <span class="formula">
    `D^k x^n // n! = {
        x^(n-k) // (n-k)!, k le n;
        0, "otherwise";
    :}`
  </span>
</p>

<p class="theorem">
  <b>多项展开</b>
  <span class="formula">
    `(sum_(i=1)^m x_i)^n = sum_(|alpha| = n) (n!)/(alpha!) bm x^alpha`.
  </span>
  对 `bm x` 的维数 `m` 作归纳, 并使用二项式定理即可证明此公式.
  其中 `(n!)/(alpha!)` 称为<b>多项式系数</b>.
  此公式的项数是方程 `|alpha| = n` 的非负整数解数, 等于 `(n+m-1;n)`.
</p>

<p class="example">
  <b>多项展开公式中的组合学</b>
  `m = n = 3` 时, 多项展开有 10 项:
  <span class="formula">
    `(a+b+c)^3`
    `= a^3+b^3+c^3`
    `+ 3a^2 b + 3b^2 c + 3c^2 a + 3a b^2 + 3b c^2 + 3c a^2`
    `+ 6a b c`.
  </span>
  利用对称求和, 简写为
  <span class="formula">
    `(a+b+c)^3 = sum_(sym) a^3 + 3 sum_(sym) a^2 b + 6 a b c`.
  </span>
  展开式中的次数
  <span class="formula">
    `3 = 2 + 1 = 1+1+1`
  </span>
  穷举了 3 的分拆.
  `sum_(sym) a^3 b^0 c^0` 中各次数出现的次数为 `1, 2` (次数 3 出现 1 次,
  次数 0 出现 2 次), 因此它包含
  `(3; 1","2) = 3` 项;
  `sum_(sym) a^2 b^1 c^0` 中各次数出现的次数为 `1, 1, 1`, 因此它包含
  `(3; 1"," 1"," 1) = 6` 项.
  同理
  <span class="formula">
    `(a+b+c+d)^4`
    `= sum_(sym) a^4 + 4 sum_(sym) a^3 b + 6 sum_(sym) a^2 b^2
    + 12 sum_(sym) a^2 b c + 24 a b c d`
  </span>
  4 的分拆为
  <span class="formula">
    `4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1`.
  </span>
  两边的项数为
  <span class="formula">
    `(7;3) = (4; 1"," 3) + (4; 1"," 1"," 2) + (4; 2"," 2) + (4; 1"," 2"," 1) + (4; 4)`.
  </span>
</p>

<p class="theorem" id="the-carlson-inequality">
  <b>Carlson 不等式</b> 设 `x_1, cdots, x_n` 为非负整数, 则
  <span class="formula">
    `sum_(j=1)^m (prod_(k=1)^n x_(j k))^(1/n)`
    `le prod_(k=1)^n (sum_(j=1)^m x_(j k))^(1/n)`.
  </span>
  `n = 2` 时, 即为 Cauchy 不等式.
</p>

<p class="proof">
  令 `y_j = (prod_(k=1)^n x_(j k))^(1/n)`, `lambda_(j k) = x_(j k)//y_j`,
  原不等式化为
  <span class="formula">
    `(sum_(j=1)^m y_j)^n le prod_(k=1)^n sum_(j=1)^m lambda_(j k) y_j`.
  </span>
  使用多项展开, 左边为 `sum_(|alpha|=n) n!/alpha! y^alpha`, 右边为 `sum_(|alpha|=n) k_alpha y^alpha`.
  为了确定其中系数 `k_alpha`, 考虑乘积
  <span class="formula">
    `(sum_(j_1) lambda_(j_1 1) y_(j_1)) cdots (sum_(j_n) lambda_(j_n n) y_(j_n))`
  </span>
  中 `y_1^1 y_2^6 y_3^5` 项的系数. 这个系数形如
  `sum lambda_(j_1 1) cdots lambda_(j_n n)`,
  因为 `y_1` 的次数是 1, 所以下标 `j_1, cdots, j_n` 中, `y_1` 的下标 "1"
  出现的次数是 1. 同理 "2" 出现的次数是 6, "3" 出现的次数是 5. 总之,
  <span class="formula">
    `k_alpha = sum lambda_(j_1 1) cdots lambda_(j_n n)`,
  </span>
  其中下标 `j_1, cdots, j_n` 中, `1` 出现的次数为 `alpha_1`, ...,
  `m` 出现的次数为 `alpha_m`. 且求和的总项数为 `n!/alpha!`.
  下证 `n!/alpha! le k_alpha`, 从而原不等式成立.
  事实上, 记 `N = n!/alpha!`. 由均值不等式
  <span class="formula">
    `1/N sum lambda_(j_1 1) cdots lambda_(j_n n)`
    `ge (prod lambda_(j_1 1) cdots lambda_(j_n n))^(1/N)`.
  </span>
  上式右边所有系数 `lambda` 恰好各出现一次, 取 `N` 次方后, 等于
  <span class="formula">
    `prod_(j k) lambda_(j k)`
    `= prod_(j=1)^m prod_(k=1)^n x_(j k)/y_j`
    `= prod_(j=1)^m y_j^n/y_j^n = 1`.
  </span>
  证毕.
</p>

<h2>排列与组合的算法</h2>

<script src="../../js/note.js?type=math"></script>
</body>
</html>
